#include "headfiles.h"

using namespace std;

bool wordBreak(string s, unordered_set<string> &dict) {
    bool flag = true;
    int i, word_start = 0;
    
    while (flag) {
        flag = false;
        for (i = word_start + 1; i <= s.length(); i++) {
            auto wit = dict.find(s.substr(word_start, i - word_start));
            if (wit != dict.end()) {
                word_start = i;
                flag = true;
                if (i == s.length()) {
                    return true;
                }

                break;
            }
        }
    }

    flag = true;
    word_start = 0;
    while (flag) {
        flag = false;
        for (i = s.length(); i >= word_start; i--) {
            auto wit = dict.find(s.substr(word_start, i - word_start));
            if (wit != dict.end()) {
                word_start = i;
                flag = true;
                if (i == s.length()) {
                    return true;
                }

                break;
            }
        }
    }

    return false;
}

static void wordBreakRecur(string &s, 
                           int word_start, 
                           unordered_set<string> &dict, 
                           string word_list, 
                           vector<string> &output) {
    int i;
    for (i = word_start + 1; i <= s.length(); i++) {
        auto wit = dict.find(s.substr(word_start, i - word_start));
        if (wit != dict.end()) {
            if (i == s.length()) {
                word_list.append(s.substr(word_start, i - word_start));
                output.push_back(word_list);
                return;
            }
            
            string tmp(word_list);
            tmp.append(s.substr(word_start, i - word_start));
            tmp.append(" ");
            wordBreakRecur(s, i, dict, tmp, output);
        }
    }

    return;
}

vector<string> wordBreakAll(string s, unordered_set<string> &dict) {
    int word_start;
    string word_list;
    vector<string> output;
    wordBreakRecur(s, 0, dict, word_list, output);
 
    return output;
}

typedef struct LNode_ {
    struct LNode_ *next;
    struct LNode_ *par;
    int end;
    LNode_() : 
        next(NULL), 
        par(NULL), 
        end(0) {
    };
} LNODE;

vector<string> wordBreakAll1(string s, unordered_set<string> &dict) {
    LNODE *head = NULL;
    LNODE *prev_head, *cur, *word_head;
    vector<string> output;
    int i, start;
    size_t length = s.length();
    for (i = 1; i <= length; i++) {
        auto wit = dict.find(s.substr(0, i));
        if (wit != dict.end()) {
            LNODE *n = new LNODE;
            n->end = i;
            n->par = head;
            head = n;
        }

        word_head = prev_head = head;
        while (word_head) {
            cur = word_head;
            while (cur) {
                if (i > cur->end) {
                    auto wit = dict.find(s.substr(cur->end, i - cur->end));
                    if (wit != dict.end()) {
                        LNODE *n = new LNODE;
                        n->end = i;
                        n->next = cur;
                        n->par = word_head->par;
                        if (word_head == head) {
                            head = n;
                        }
                        else {
                            prev_head->par = n;
                        }
                        prev_head = word_head = n;
                    }
                }
                cur = cur->next;
            }
            prev_head = word_head;
            word_head = word_head->par;
        }
    }

    // Construct the output
    string word_list;
    word_head = head;
    while (word_head) {
        // This is a output
        if (word_head->end == length) {
            word_list.clear();
            cur = word_head;
            while (cur->next) {
                word_list.append(s.substr(cur->next->end, cur->end - cur->next->end));
                word_list.append(" ");
                cur = cur->next;
            }
            word_list.append(s.substr(0, cur->end));
            output.push_back(word_list);
        }
        word_head = word_head->par;
    }

    // Remove the linked list
/*
    LNODE *next;
    word_head = head;
    while (word_head) {
        cur = word_head;
        LNODE *tmp1 = cur->par;
        while (cur) {
            LNODE *tmp2 = cur->next;
            delete cur;
            cur = tmp2;
        }
        word_head = tmp1;
    }
*/
    return output;
}

